javascript实现堆排序 |
您所在的位置：网站首页 › js 排序 › javascript实现堆排序 |
javascript实现堆排序
|
堆排序 堆排序基本介绍1.堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。2.堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。3.每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆 关于用数组与二叉树结构转换，可以参照 堆排序的基本思想是：1.将待排序序列构造成一个大顶堆2.此时，整个序列的最大值就是堆顶的根节点。3.将其与末尾元素进行交换，此时末尾就为最大值。4.然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。 可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.   /**
*
堆排序
堆排序基本介绍
1.堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
2.堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。
3.每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
堆排序的基本思想是：
1.将待排序序列构造成一个大顶堆
2.此时，整个序列的最大值就是堆顶的根节点。
3.将其与末尾元素进行交换，此时末尾就为最大值。
4.然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
*
*/
let arr = [4, 6, 8, 5, 9, -1, 17, 5, 23, 11, 6];
heapSort(arr);
console.log(arr)
//编写一个堆排序
function heapSort(arr) {
let temp;
//1.将无序序列构成一个堆，根据升序降序需求选择大顶堆或小顶堆
//最后一个值的序号为arr.length-1，根据顺序存储二叉树，
//n节点的左子树为2*n+1,右子树为2*n+2，
//那么最后一个非叶子节点的值应该为Math.floor((arr.length-1-1)/2)
//= Math.floor((arr.length)/2 -1)
//=Math.floor(arr.length / 2) - 1
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length)
}
//2.将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端
//3.重新调整结构，使其满足堆条件，然后继续交换堆顶元素和当前末尾元素,
// 反复执行调整+交换步骤，直到整个序列有序
for (let j = arr.length - 1; j > 0; j--) {
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
}
//将一个数组(二叉树),调整成一个大顶堆
/**
* 将以i对应的非叶子节点的树调整成一个大顶堆
* @param {要调整的数组} arr
* @param {表示非叶子节点在数组中的索引} i
* @param {对多少个元素进行调整，length是在逐渐减少} length
*/
function adjustHeap(arr, i, length) {
let temp = arr[i];//先取出当前元素的值，保存在临时变量
//开始调整
//说明 调整非叶子节点的顺序时从下到上，从左到右
//从最下层开始，逐层将大的值往上提
//1.k=i*2+1是i节点的左子节点
for (let k = i * 2 + 1; k
|
【本文地址】
今日新闻 |
推荐新闻 |